//============================================================================
// Name        : All1.cpp
// Author      : hoyt.tian
// 给定正整数n，给出0~n之间所有整数10进制形式下各位包含1的个数，例如，n=12时，有1,10,11,12包含1，结果为5
//============================================================================

#include <iostream>
using namespace std;



int caculate(int n){   //返回给定数中各位出现1的个数之和

    int sum = 0;
    while(n>10){              //当给定数大于10时，考察末位是否为1
          if(n%10 == 1)    //末位位1，则累计值增加
                  sum++;
           n = n/10;        //考察下一位
    }

   if( n == 10 || n == 1)
         sum++;
   return sum;

}
/*
*   迭代考察每一个数包含1的个数
*/

int count1(int n){
   int sum = 0;
   for(int i=1; i<=n; i++)           //逐个考察1至n的所有数，并将其中1的个数累计
          sum += caculate(i);
   return sum;
}


/*
 *   分部递归的解决方案
 */

int count1_ex(int n){
	if(n<1)
		return 0;
	if(n < 10){
		return 1;
	}else if(n < 100){
		if(n>19){
			return 12+(n/10-2)+(n%10==0?0:1);
		}else{
			int b = n%10;
			return 2 + (b==0?0:(b+1));
		}
	}

	int dec = 10;
	for(; n/dec>0; dec*=10)
		;
	dec = dec/10;
	int a = n/dec;
	int lower_sum = count1_ex(dec-1);
	int small_part = n-a*dec;
	return (a>1?1:0)*dec + a*lower_sum + (a==1?(count1_ex(small_part)+small_part+1):count1_ex(small_part));

}

int main() {
	int i = 0;
	cout << "Please input test number"<<endl;
	cin >> i;
	while(i>0){
		cout << " Count "<<i <<", with count1_ex:"<<count1_ex(i)<<", with count1:"<<count1(i)<<endl;
		cin >> i;
	}
	return 0;
}
